The need for cryptography dates to the earliest use of written language. The need to keep messages private gave rise to the science of cryptography. Ciphers were used for safeguarding military secrets in Roman times. Over the years, cryptography has become more and more sophisticated. Today a vast amount of information is being transmitted digitally for both military and commercial purposes. Prudence dictates that much of this information be kept private.
At least some transmitted data exists in the form of binary data files. A binary data file is generally distinguished from a text file in that each byte of data can represent many more combinations than the usual 128 characters of text associated with the ASCII or similar character set. A digitized image, for example, is normally in the form of a binary file. Technically speaking, all eight bits in a byte are used in a binary file. Consequently, 256 (2.sup.8) different binary patterns may be encoded. In text, however, normally only seven of eight possible bits are employed, resulting in the 128 (2.sup.7) possible characters.
Practical transmission of large, binary data files requires fast and robust encryption techniques. Current software implementations of the most popular encryption methods or algorithms, such as Rivest, Shamir, Adleman (RSA), El Gamal, or Data Encryption Standard (DES), do not provide encryption rates suitable for use with large data files, such as images.
Moreover, the security of most public key cryptographic schemes, such as RSA, or El Gamal, is based on the difficulty of performing factorization of large numbers, or in solving discrete logarithm problems in a fast, efficient manner. Recent advances in algorithmic techniques, number theory, and distributed computing, not to mention the availability of powerful but inexpensive personal computers, have seriously challenged the basis of these techniques. In addition to that, the newly emerged field of quantum computing could, theoretically, make those methods totally unusable in the future. Also, the need for alternative, secure and fast encryption techniques for transfer and archival of large amounts of data increases quickly with the growing access to and use of the Internet.
A new class of encryption techniques based on two- and three-dimensional chaotic maps is described in the present invention. Chaotic maps, representative of images or data, provide excellent security and have other desired cryptographic qualities. For example, both the hardware and software necessary to implement the techniques of the present invention are simple. This simplicity results in high efficiency which, in turn, produces high encryption rates.
Two desirable cryptographic properties of chaotic maps are sensitivity to initial conditions and parameters, and mixing (topological transitivity). Sensitivity to initial conditions means that when a chaotic map is iteratively applied to two initially close points of data in an array, the points quickly diverge, and eventually become uncorrelated. Sensitivity to parameters causes the properties of the map to change quickly when the parameters on which the map depends are slightly perturbed.
Mixing, or topological sensitivity, is the tendency of the system to quickly "scramble up" small portions of the state space into an intricate network of filaments. Local, correlated information becomes scattered all over the state space.
All of these properties suggest that chaotic maps constrained to a discrete, two-dimensional lattice could be used to generate complicated transformations of data, such as pixels including gray levels of a digital image. Indeed, it is possible to modify certain invertible two-dimensional maps on a torus or on a rectangle for the purpose of image encryption.